import com.sun.xml.internal.ws.addressing.WsaActionUtil;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TestbinaryTree {//定义二叉树的类
    static class TreeNode{//定义结点
        public char val;
        public TreeNode left;//孩子结点，所以用TreeNode类型的引用
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public TreeNode root;//每个二叉树都有一个根节点
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        this.root = A;
        return root;
    }
    //前序遍历：根——》左子树——》右子树
    public void preOrder(TreeNode root){
        if(root == null){//递归的开始也是结束条件
            return ;//若根节点为空，则直接返回
        }
        System.out.print(root.val+" ");//若根不为空，先输出跟结点
        preOrder(root.left);//通过调用自己，实现递归，遍历左子树
        preOrder(root.right);
    }
  /*  List<Integer> ret = new ArrayList<>();//用来记录遍历的结点的值
    public List<Integer> preorderTraversal(TreeNode root){
        if(root == null){
            return ret;//根节点为空，返回ret;
        }
        //System.out.println(root.val+" ");
        ret.add(root.val);//将根节点的值，放到ret当中
        preorderTraversal(root.left);//遍历左子树
        preorderTraversal(root.right);//遍历右子树
        return ret;
    }*/
//    public List<Integer> preorderTraversal(TreeNode root){
//       List<Integer> ret = new ArrayList<>();
//       func(root,ret);
//       return ret;
//    }
//    //递归是由这个方法完成的
//    public void func(TreeNode root,List<Integer> ret){
//        if(root == null){
//            return;
//        }
//        ret.add(root.val);
//        func(root.left,ret);
//        func(root.right,ret);
//    }
    //public List<Integer> ret = new ArrayList<>();//用来记录遍历的结点的值
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList<>();//每次调用这个方法，都会产生新的空间。
        if (root == null) {
            return ret;//根节点为空，返回ret;
        }
//        System.out.println(root.val+" ");
        ret.add(root.val);//将二叉树的第一个根节点的值，放到ret当中
        List<Character> leftTree = preorderTraversal(root.left);//遍历左子树，并用List<Integer>类型的引用来接收方法的返回值
        ret.addAll(leftTree);//addAll方法用来向ret集合中添加一个集合对象所包含的所有内容

        List<Character> rightTree = preorderTraversal(root.right);//遍历右子树
        ret.addAll(rightTree);

        return ret;
    }


    //中序遍历：左子树——》根节点——》右子树
    public void inOrder(TreeNode root){
        if(root == null){//递归的开始和结束条件
            return;//若根节点为空，则返回
        }
        inOrder(root.left);//若根节点不为空，则递归左子树
        System.out.print(root.val+" ");//左子树递归完成，打印根节点
        inOrder(root.right);//再递归右子树
    }

    //后序遍历：左子树——》右子树——》根节点
    public void postOrder(TreeNode root){
        if(root == null){//递归的开始和结束条件
            return;//若根节点为空，则返回
        }
        postOrder(root.left);//若根节点不为空，则递归左子树
        postOrder(root.right);//再递归右子树
        System.out.print(root.val+" ");//左右子树都递归完成，打印根节点

    }
    //计算二叉树的总结点 1.子问题思路
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftSize = size(root.left);//这里的递归，每次走左边结点，查看子树的左右结点，然后将子树的左右结点加根节点的值返回。
        int rightSize = size(root.right);
        return leftSize + rightSize + 1;
    }
    //遍历思路
    public int nodeSize;
    public void size1(TreeNode root){
        if(root == null){
            return ;
        }
        nodeSize++;
        size1(root.left);
        size1(root.right);
    }
    //二叉树的叶子节点
    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.right == null&&root.left == null){
            return 1;
        }
        int leftSize = getLeafNodeCount(root.left);
        int rightSize = getLeafNodeCount(root.right);
        return leftSize+rightSize;
    }
    public int leafSize;
    public void getLeafNodeCount2(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left == null&&root.right == null){
            leafSize++;//遍历一个叶子节点+1
        }
        getLeafNodeCount2(root.left);//调用该方法遍历左子树。
        getLeafNodeCount2(root.right);
    }
    //获取第k层结点的个数
    public int getLevelNodeCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        int leftSize = getLevelNodeCount(root.left,k-1);
        int rightSize = getLevelNodeCount(root.right,k-1);
        return leftSize+rightSize;
    }
    //获取二叉树的高度
    public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        int minHeight = leftHeight>rightHeight?leftHeight:rightHeight;
        return minHeight+1;
    }
    //检测值为val的元素是否存在
    public TreeNode find(TreeNode root,int val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;//每次遍历之后，都相当于用子树的根节点的值来进行对比。
        }
        TreeNode leftTree = find(root.left,val);
        if(leftTree != null){
            return leftTree;
        }
        TreeNode rightTree = find(root.right,val);
        if(rightTree != null){
            return rightTree;
        }
        return null;//表示没有找到
    }
    //检测值为value的元素是否存在
    public TreeNode find1(TreeNode root,int val){
        if(root == null){
            return null;//若根节点不为空，则程序向下执行
        }
        if(root.val == val){//判断根节点的值，是否和要查找的值相同
            return root;//找到val值，就返回，程序结束。
        }
        TreeNode leftTree1 = find1(root.left,val);//递归root的左子树
        if(leftTree1 != null){//如果左子树不为空，那么在左数中要么存在要查找的val值，要么返回的是null，
            return leftTree1;//leftTree1中的内容要么是要查找的val值，要么就是null
        }
        TreeNode rightTree1 = find1(root.right,val);
        if(rightTree1 != null){
            return rightTree1;
        }
        return null;//没有找到val值的结点
    }
    //判断两个二叉树是否相等
    public boolean isSameTree(TreeNode p,TreeNode q){
        if(p == null && q == null){//1、两个数都为空，则相同
            return true;
        }
        if(p == null && q != null || p != null && q == null){
            return false;//2、两个树一棵为空，一棵不为空，则不相同
        }
        //3、树的结构相不相同，存在三种情况，前两种都不满足的情况下，只剩两个树都不为空的情况
        //所以这里要对树的结点的值进行判断是否相同，若树中结点的值相同，则两棵树相同
        if(p.val != q.val){
            return false;
        }
        //将满足树相同的所有条件都写完之后，就通过递归遍历两棵树
        //两棵树左子树和右子树都相同的情况下，返回true，否则返回false
        return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
    }
    //判断一个树，是否为另一个树的子树
    public boolean isSubtree(TreeNode root,TreeNode subRoot) {
        if(root == null ||subRoot == null){
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        if (isSubtree(root.left, subRoot)) {
            return true;
        }
        if (isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }
    public TreeNode invertTree(TreeNode root){
        if(root == null){//首先判断二叉树的跟结点是否为空
            return null;
        }
        //根节点不为空，则通过结点tmp将root的左树和右树进行交换
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        //通过递归将 整颗二叉树的左右结点都交换
        invertTree(root.left);//这里不写接收返回值的引用是因为，通过代码已将子树位置交换，没有必要传给根节点。
        invertTree(root.right);

        return root;//返回交换后的树
    }
    //是否为平衡树
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }
        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);
        return Math.abs(leftH - rightH) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }
    public boolean isBalanced1(TreeNode root){
        return maxDepth1(root) >= 0;
    }
    public int maxDepth1(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
       if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <= 1){
           return Math.max(leftHeight,rightHeight)+1;
       }else{
           return -1;
       }
    }
    public boolean isSymmetric(TreeNode root){
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode p,TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p == null && q != null || p != null && q == null){
            return false;
        }

        if(p.val != q.val){
            return false;
        }

        return isSymmetricChild(p.left,q.right)&& isSameTree(p.left,q.right);
    }

    public void levelOrder(TreeNode root){
        if(root == null){
            return ;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> list = new LinkedList<>();//定义一个二维数组
        if(root == null){
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();//创建一个队列
        queue.offer(root);//先将根节点放入队列
        while(!queue.isEmpty()){//再判断队列是否为空
            int size = queue.size();//求队列当中的数据个数
            List<Integer> tmp = new ArrayList<>();//这里创建一个顺序表tmp，通过每次循环创建新的顺序表，作为二维数组的元素
            while(size != 0){//通过判断队列当中元素的个数，来判断循环几次，这个while循环每次结束之后，将tmp作为元素，放入到二维数组list当中
                TreeNode cur = queue.poll();
                tmp.add(cur.val);//这里将出队列的元素，放入每次循环创建的顺序表中，用来做顺序表的元素
                size --;
                if(cur.left != null){//将出队列元素的左孩子节点放入队列中
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);//将每个tmp顺序表作为元素放入到二维数组list当中
        }
        return list;//将二叉树遍历完成，最终返回二维数据即可得到层序遍历的结果
    }














}
